

export interface Point {
    x: number;
    y: number;
}

export class ANode {
    // point:Point;
    x: number;
    y: number;
    pre: ANode;
    f: number; // 启发函数
    g: number; // 代价
    h: number; // 启发因子 

    constructor(x: number, y: number, endP: Point) {
        this.x = x;
        this.y = y;
        this.h = (Math.abs(this.x - endP.x) + Math.abs(this.y - endP.y)) * 10;
        this.g = 0;
        this.f = this.h;
    }
}

/**
 * 1.Astar
 * 2.sdk
 * 3.plist加载
 * 4.启动进度条加载在做什么
 * 5.1024*1024
 * 6.retain
 */

export class AStar {
    constructor(srcData?: number[][]) {
        if (srcData)
            this.setData(srcData);
        this.xiePassAble = false;
    }

    public xiePassAble: boolean; //斜方向时，途中有障碍，能否穿过

    // [2]
    // @property
    // serializableDummy = 0;
    // 对角方向索引是偶数
    readonly direction: Point[] = [
        { x: -1, y: 1 }, //左上
        { x: 0, y: 1 }, //上
        { x: 1, y: 1 }, //右上
        { x: -1, y: 0 }, //左
        { x: -1, y: -1 }, //左下
        { x: 1, y: 0 }, //右
        { x: 1, y: -1 }, //右下
        { x: 0, y: -1 }, //下
    ];
    mapData: number[][] = [];

    end: Point = null;

    // 0 可通过    1 障碍
    setData(srcData: number[][]) {
        this.mapData = [];
        for (let col = 0; col < srcData.length; col++) {
            this.mapData[col] = [];
            for (let row = 0; row < srcData[0].length; row++) {
                this.mapData[col][row] = srcData[row][col];
            }
        }
    }

    getPath(to: ANode): Point[] {
        let path: Point[] = [];

        // let node:Point = ;
        // path.push({x:this.end, y:this.end});
        // path.splice(0, 0, { x: to.pre.x, y: to.pre.y });

        while (to !== undefined) {
            path.splice(0, 0, { x: to.x, y: to.y });
            to = to.pre;
        }

        return path;
    }

    run(from: Point, to: Point): Point[] {
        this.end = to;

        let open: ANode[] = [];        // Open有序列表
        let openMap: Map<number, ANode> = new Map(); // 用于查看open表里有没有该数据
        let close: Set<number> = new Set();

        open.push(new ANode(from.x, from.y, to));

        let select: ANode;
        let dirNum = this.direction.length;
        while (open.length > 0) {
            select = open[0];
            // console.log(" --> " + select.x + " " + select.y);
            // 找到
            if (select.x == to.x && select.y == to.y) {
                // console.log("找到目标：" + select.x + "," + select.y);
                return this.getPath(select);
            }

            // 从open表移除，加入close表
            open.splice(0, 1);

            const curKey = select.x * this.mapData.length + select.y;
            openMap.delete(curKey);
            close.add(curKey);  // x*100 + y 作为key
            // console.log("select key:" + select.x * 100 + select.y);

            for (let dirIdx = 0; dirIdx < dirNum; dirIdx++) {
                let next: ANode = this.getOneRoundNode(select, dirIdx);

                if (!next) continue;

                // close表不处理
                const nextKey = next.x * this.mapData.length + next.y;
                if (!close.has(nextKey)) {
                    // let idx = this.containsNode(next, open)
                    // if (idx < 0) {  // 不在open表也不在close表
                    let nextInOpen = openMap.get(nextKey);
                    if (nextInOpen === undefined) {
                        openMap.set(nextKey, next);
                        this.pushByAscending(next, open);
                    }
                    else if (next.f < nextInOpen.f)   // 在open表中, 若f小，更新f
                    {
                        nextInOpen.g = next.g;
                        nextInOpen.f = next.f;
                        nextInOpen.pre = next.pre;
                    }
                }
            }
        }
    }


    // IsNullOrUndefined(value:any):boolean{
    //     return value === undefined || value === null;
    // }

    // 升序插入
    pushByAscending(target: ANode, arr: ANode[]) {
        let index = arr.length - 1;
        for (; index >= 0; index--) {
            if (target.f < arr[index].f)
                arr[index + 1] = arr[index];
            else
                break;
        }
        arr[index + 1] = target;
    }

    getOneRoundNode(select: ANode, dirIdx: number): ANode {
        let dir: Point = this.direction[dirIdx]

        let x: number = select.x + dir.x;
        let y: number = select.y + dir.y;

        // 无效坐标
        if (this.mapData[x] === undefined || this.mapData[x][y] === undefined) {
            // console.log("无效坐标:" + x + "," + y);
            return null;
        }

        // 是障碍
        if (this.mapData[x][y] > 0) {
            // console.log("障碍坐标:" + x + "," + y);
            return null;
        }

        // 对角是障碍
        if (!this.xiePassAble)
            if (this.mapData[x][select.y] > 0 || this.mapData[select.x][y] > 0) {
                // console.log("对角是障碍:" + x + "," + y);
                return null;
            }

        let node: ANode = new ANode(x, y, this.end)

        // 斜向 
        if (dirIdx % 2 === 0)
            node.g = select.g + 14;
        else
            node.g = select.g + 10;

        node.f = node.g + node.h;
        node.pre = select;

        return node;
    }

    changeXiePassAble(able: boolean) {
        this.xiePassAble = able;
    }

    // 检查坐标相同
    containsNode(node: ANode, array: ANode[]): number {
        for (let i = 0; i < array.length; i++) {
            if (node.x == array[i].x && node.y == array[i].y)
                return i;
        }

        return -1;
    }

    // update (deltaTime: number) {
    //     // [4]
    // }
}

